package com.peng.leetcode.minknum;


/**
 * MinKNum
 *
 * @author lupeng
 * Created on 2022-02-15
 */
public class MinKNum {

    public static void main(String[] args) {
        int[] arr = new int[] {4,5,3,2,1};
        int[] leastNumbers = new MinKNum().getLeastNumbers(arr, 2);
        for (int leastNumber : leastNumbers) {
            System.out.println(leastNumber);
        }
    }

    public int[] getLeastNumbers(int[] arr, int k) {
        find(arr, 0, arr.length - 1, k);
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    private void find(int[] arr, int left, int right, int k) {
        if (left >= right) {
            return;
        }
        int pos = partition(arr, left, right);
        if (pos == (k - 1)) {
            return;
        } else if (pos < (k - 1)) {
            find(arr, pos + 1, right, k);
        } else {
            find(arr, left, pos - 1, k);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int value = arr[right];
        int i = left;
        int j = left;
        while (j < right) {
            if (arr[j] < value) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
            j++;
        }
        int temp = arr[i];
        arr[i] = arr[right];
        arr[right] = temp;
        return i;
    }

}
